#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    int numDecodings(string s);
    bool isLegal(char a, char b);
};

// 动态方程：
// dp[i] = dp[i - 2] : dp[i - 1] : dp[i - 1] + dp[i - 2];
// 需要考虑的情况太多，怎么才能一次考虑周全呢？
// 把所有情况全部列出来，做到不遗漏、不重复。
// 这也是一个明确需求的过程，避免答非所问

int Solution::numDecodings(string s) {
    if('0' == s[0]) return 0; // 09
    if(s.size() == 1) return 1; // 9
    int dp[s.size()];
    dp[0] = 1;
    if(s[1] == '0') {
        if(!isLegal(s[0], s[1])) return 0; // 30*
        else dp[1] = 1; // 20*
    } else isLegal(s[0], s[1]) ? dp[1] = 2 : dp[1] = 1; // 11* // 27*
    for(int i = 2; i < s.size(); ++i) {
        if('0' == s[i]) {
            if('0' == s[i - 1] || !isLegal(s[i - 1], s[i])) return 0; // 30
            else dp[i] = dp[i - 2]; // 110
        } else if('0' == s[i - 1] || !isLegal(s[i - 1], s[i])) {
            dp[i] = dp[i - 1]; // 1106 // 322
        } else {
            dp[i] = dp[i - 1] + dp[i - 2]; // 111
        }
    }
    return dp[s.size() - 1];
}

bool Solution::isLegal(char a, char b) {
    int value = 10 * (a - '0') + (b - '0');
    // // C++ string构造函数和析构函数详解 http://c.biancheng.net/view/1443.html
    // string s(1, a), t(1, b), u;
    // u = s + t;
    // value = stoi(u);
    if(value <= 26) return true;
    else return false;
}

class NumDecodingsCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(NumDecodingsCheck, testNumDecodings_1) {
    string s("27");
    EXPECT_TRUE(1 == solution.numDecodings(s));
}

TEST_F(NumDecodingsCheck, testNumDecodings_2) {
    string s("226");
    EXPECT_TRUE(3 == solution.numDecodings(s));
}

TEST_F(NumDecodingsCheck, testNumDecodings_3) {
    string s("2030235312");
    EXPECT_TRUE(0 == solution.numDecodings(s));
}

TEST_F(NumDecodingsCheck, testNumDecodings_4) {
    string s("2342354312");
    EXPECT_TRUE(8 == solution.numDecodings(s));
}

TEST_F(NumDecodingsCheck, testNumDecodings_5) {
    string s("11106");
    EXPECT_TRUE(2 == solution.numDecodings(s));
}

TEST_F(NumDecodingsCheck, testNumDecodings_6) {
    string s("10011");
    EXPECT_TRUE(0 == solution.numDecodings(s));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
